package 算法.leetcode.bytedance.字符串;

import java.util.ArrayList;
import java.util.List;

/**
 * 有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
 *
 * 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
 * 给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。
 * 你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
 * @author lchenglong
 * @date 2023/2/14
 */
public class 复原IP地址 {
    public static class Solution {

        public static void main(String[] args) {
            Solution solution = new Solution();
            List<String> ans = solution.restoreIpAddresses("25525511135");
            ans.forEach(System.out::println);
        }
        // 符合条件的ip地址
        List<String> ans = new ArrayList<>();
        String s ;
        public List<String> restoreIpAddresses(String s){
            this.s = s;
            // 存放ip,用来回溯及保存
            String[] ips = new String[4];
            dfs(0,0,ips);
            return ans;
        }

        public void dfs(int start,int cur,String[] ips) {
            if (start == 4 && cur == s.length()){
                // 为正确✅的ip
                StringBuilder ip = new StringBuilder();
                for (int i=0;i<4;i++) {
                    ip.append(ips[i]).append(".");
                }
                ip.delete(ip.length()-1,ip.length());
                ans.add(ip.toString());
            }
            // 读取了4个ip段,但是没遍历完,不符合条件,直接返回
            if (start == 4 && cur!=s.length())return;
            // 每个ip最大255 所以最长3位
            for (int i=cur;i<cur + 3 && i<s.length();i++){
                // 读取ip地址
                String temp = s.substring(cur, i+1);
                if (Integer.parseInt(temp)<=255) {
                    // 是ip地址
                    ips[start] = temp;
                    // 读取下一个ip段
                    dfs(start+1,i+1,ips);
                    // 回溯
                    ips[start] = "";
                }
                // 01,021等都是不符合条件的ip段
                if ("0".equals(temp))break;
            }
        }
    }

}
